/**
 * https://leetcode.cn/problems/path-sum-iii/
 */
function pathSum(root: TreeNode | null, targetSum: number): number {
  if (root === null) return 0;

  let ans = findTargetSum(root, targetSum);

  ans += pathSum(root.left, targetSum);
  ans += pathSum(root.right, targetSum);

  return ans;
}

const findTargetSum = (node: TreeNode | null, leftSum: number) => {
  let ans = 0;
  if (node === null) {
    return ans;
  }

  const val = node.val;
  if (val === leftSum) {
    ans++;
  }

  ans += findTargetSum(node.left, leftSum - val);
  ans += findTargetSum(node.right, leftSum - val);

  return ans;
};
